/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/heaters
   @Language: C++
   @Datetime: 19-05-22 09:35
   */

class Solution {
public:
	/**
	 * @param houses: positions of houses
	 * @param heaters: positions of heaters
	 * @return: the minimum radius standard of heaters
	 */
	int findRadius(vector<int> &houses, vector<int> &heaters) {
		// Write your code here
		int res=0;
		sort(heaters.begin(),heaters.end());
		for(int i=0; i<houses.size(); ++i){
			int j=lower_bound(heaters.begin(),heaters.end(),houses[i])-heaters.begin();
			int r=INT_MAX;
			if(j<heaters.size()) r=heaters[j]-houses[i];
			if(j>0) r=min(r,houses[i]-heaters[j-1]);
			res=max(res,r);
		}
		return res;
	}
};
